package org.xqh.study.leetcode.algorithm.graph;

import java.util.Arrays;

/**
 * @ClassName MaxNumEdgesToRemove
 * @Description 最大可删除边数
 *   https://leetcode-cn.com/problems/remove-max-number-of-edges-to-keep-graph-fully-traversable/
 * @Author xuqianghui
 * @Date 2021/1/27 11:47
 * @Version 1.0
 */
public class MaxNumEdgesToRemove {

//    Alice 和 Bob 共有一个无向图，其中包含 n 个节点和 3  种类型的边：
//
//    类型 1：只能由 Alice 遍历。
//    类型 2：只能由 Bob 遍历。
//    类型 3：Alice 和 Bob 都可以遍历。
//    给你一个数组 edges ，其中 edges[i] = [typei, ui, vi] 表示节点 ui 和 vi 之间存在类型为 typei 的双向边。
//    请你在保证图仍能够被 Alice和 Bob 完全遍历的前提下，找出可以删除的最大边数。
//    如果从任何节点开始，Alice 和 Bob 都可以到达所有其他节点，则认为图是可以完全遍历的。
//
//    返回可以删除的最大边数，如果 Alice 和 Bob 无法完全遍历图，则返回 -1 。
    public static int maxNumEdgesToRemove(int n, int[][] edges) {
        UnionFindA ufa = new UnionFindA(n);
        UnionFindA ufb = new UnionFindA(n);
        int ans = 0;//可以删除的边
        for(int[] edge:edges){
            --edge[1];
            --edge[2];
        }
        //处理公共边
        for(int[] edge:edges){
            if(edge[0] == 3){
               boolean flag = ufa.union(edge[1], edge[2]);
               if(flag){
                   //可以合并  并查集ufb 重复合并一次
                   ufb.union(edge[1], edge[2]);
               }else {
                   ans ++;
               }
            }
        }

        //处理独占边
        for(int[] edge:edges){
            if(edge[0] == 1){//Alice独占边
                if(!ufa.union(edge[1], edge[2])){
                    ans ++;
                }
            }else if(edge[0] == 2){//Bob独占边
                if(!ufb.union(edge[1], edge[2])){
                    ans ++;
                }
            }
        }

        //判断 两个并查集(无向图) 是否都 是连通的
        if(ufa.setCount != 1 || ufb.setCount != 1){
            return -1;//表示不可连通
        }

        return ans;
    }

    public static class UnionFindA{
        int[] parent;
        int[] size;//每个 节点的树深度
        int setCount;//连通分量个数  可连通 最终合并 setCount = 1;

        public UnionFindA(int n){
            parent = new int[n];
            size = new int[n];
            setCount = n;
            Arrays.fill(size, 1);//默认 深度都是1
            for(int i = 0; i < n ; i ++){
                parent[i] = i;
            }
        }

        public int find(int idx){
            if(parent[idx] != idx){
                parent[idx] = find(parent[idx]);
            }
            return parent[idx];
        }

        public boolean union(int x, int y){
            x = find(x);
            y = find(y);
            if(x == y){
                return false;
            }
            if(size[x] < size[y]){
                int tmp = x;
                x = y;
                y = tmp;
            }
            parent[y] = x;
            size[x] += size[y];
            --setCount;
            return true;
        }
    }

    public static void main(String[] args) {
//        int[][] edges = {{3,1},{5,7},{8,9},{8,9},{8,9}};
        int[][] edges = {{3,1,2},{3,2,3},{1,1,3},{1,2,4},{1,1,2},{2,3,4}};
        //[[3,1,2],[3,2,3],[1,1,3],[1,2,4],[1,1,2],[2,3,4]]
        Solution solution = new Solution();
        solution.maxNumEdgesToRemove(4, edges);
    }

    static class Solution {
        public int maxNumEdgesToRemove(int n, int[][] edges) {
            UnionFind ufa = new UnionFind(n);
            UnionFind ufb = new UnionFind(n);
            int ans = 0;

            // 节点编号改为从 0 开始
            for (int[] edge : edges) {
                --edge[1];
                --edge[2];
            }

            // 公共边
            for (int[] edge : edges) {
                if (edge[0] == 3) {
                    if (!ufa.unite(edge[1], edge[2])) {
                        ++ans;
                    } else {
                        ufb.unite(edge[1], edge[2]);
                    }
                }
            }

            // 独占边
            for (int[] edge : edges) {
                if (edge[0] == 1) {
                    // Alice 独占边
                    if (!ufa.unite(edge[1], edge[2])) {
                        ++ans;
                    }
                } else if (edge[0] == 2) {
                    // Bob 独占边
                    if (!ufb.unite(edge[1], edge[2])) {
                        ++ans;
                    }
                }
            }

            if (ufa.setCount != 1 || ufb.setCount != 1) {
                return -1;
            }
            return ans;
        }
    }

    // 并查集模板
    static class UnionFind {
        int[] parent;
        int[] size;
        int n;
        // 当前连通分量数目
        int setCount;

        public UnionFind(int n) {
            this.n = n;
            this.setCount = n;
            this.parent = new int[n];
            this.size = new int[n];
            Arrays.fill(size, 1);
            for (int i = 0; i < n; ++i) {
                parent[i] = i;
            }
        }

        public int findset(int x) {
            return parent[x] == x ? x : (parent[x] = findset(parent[x]));
        }

        public boolean unite(int x, int y) {
            x = findset(x);
            y = findset(y);
            if (x == y) {
                return false;
            }
            if (size[x] < size[y]) {
                int temp = x;
                x = y;
                y = temp;
            }
            parent[y] = x;
            size[x] += size[y];
            --setCount;
            return true;
        }

        public boolean connected(int x, int y) {
            x = findset(x);
            y = findset(y);
            return x == y;
        }
    }
}
